|
In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep track of the current search path.〔.〕 Versions of this algorithm have been proposed by , , , , and ; of these, Dijkstra's version was the first to achieve linear time.〔(History of Path-based DFS for Strong Components ), Hal Gabow, accessed 2012-04-24.〕 ==Description== The algorithm performs a depth-first search of the given graph ''G'', maintaining as it does two stacks ''S'' and ''P''. Stack ''S'' contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices. Stack ''P'' contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter ''C'' of the number of vertices reached so far, which it uses to compute the preorder numbers of the vertices. When the depth-first search reaches a vertex ''v'', the algorithm performs the following steps: #Set the preorder number of ''v'' to ''C'', and increment ''C''. #Push ''v'' onto ''S'' and also onto ''P''. #For each edge from ''v'' to a neighboring vertex ''w'': # * If the preorder number of ''w'' has not yet been assigned, recursively search ''w''; # *Otherwise, if ''w'' has not yet been assigned to a strongly connected component: # * *Repeatedly pop vertices from ''P'' until the top element of ''P'' has a preorder number less than or equal to the preorder number of ''w''. #If ''v'' is the top element of ''P'': # *Pop vertices from ''S'' until ''v'' has been popped, and assign the popped vertices to a new component. # *Pop ''v'' from ''P''. The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Path-based strong component algorithm」の詳細全文を読む スポンサード リンク
|